#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/*
	用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。
	队列中的元素为 int 类型。
*/

typedef struct node
{
	int data;
	struct node *up;
	struct node *down;
} Stack;

Stack *create(int n)
{
	int i;
	Stack *bottom = (Stack *)malloc(sizeof(Stack));
	bottom->down = NULL;
	Stack *top = bottom;
	for (i = 0; i < n; i++)
	{
		top->up = (Stack *)malloc(sizeof(Stack));
		top->up->down = top;
		top = top->up;
	}
	top->up = NULL;
	return bottom->up;
};

void destroy(Stack *p)
{
	Stack *up = p;
	while (up->up != NULL)
	{
		up = up->up;
	}
	while (up->down != NULL)
	{
		up = up->down;
		free(up->up);
	}
	free(up);
}

int push(Stack **tail, int data)
{
	if ((*tail)->up != NULL)
	{
		*tail = (*tail)->up;
		(*tail)->data = data;
		return 0;
	}
	else
	{
		return -1;
	}
}

int pop(Stack **head)
{
	assert((*head)->down != NULL);
	int data = (*head)->data;
	(*head) = (*head)->down;
	return data;
}

int main()
{
	Stack *stack1, *stack2;
	stack1 = create(10);
	stack2 = create(10);
	Stack *p1 = stack1, *p2 = stack2;
	// Push
	int n;
	printf("Enter an integer: ");
	scanf("%d", &n);
	int i, j;
	for (i = 0; i < n; i++)
	{
		printf("Enter number %d: ", i + 1);
		scanf("%d", &j);
		while (p2 != stack2)
		{
			push(&p1, pop(&p2));
		}
		push(&p1, j);
	}
	// Pop
	for (i = 0; i < n; i++)
	{
		while (p1 != stack1)
		{
			push(&p2, pop(&p1));
		}
		printf("%d\n", pop(&p2));
	}
	return 0;
}
